package sword.chapter8Tree;

import java.util.Map;
import java.util.TreeMap;

/**
 * 日程表
 *
 * 有序map TreeMap key：开始时间 value：结束时间
 * 画一个x时间轴，非常好理解
 *
 * @author K
 * @date 2021/12/13 15:43
 */
public class S58MyCalendar {

    private TreeMap<Integer, Integer> events;

    public S58MyCalendar() {
        events = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        // 检查头start，新日程开始时间
        // key 小于或等于 start，历史日程开始时间小于等于新日程开始时间
        // 检查历史日程结束时间（getValue）有没有框住新日程的开始时间start 即 event.getValue() > start。框住了代表日程冲突，返回false
        Map.Entry<Integer, Integer> event = events.floorEntry(start);
        if (event != null && event.getValue() > start) {
            return false;
        }

        // 检查尾end，新日程结束时间
        // key 大于或等于 start，历史日程开始时间大于等于新日程开始时间
        // 检查历史日程开始时间（getKey）有没有框住新日程的结束时间end 即 event.getKey() < end。框住了代表日程冲突，返回false
        event = events.ceilingEntry(start);
        if (event != null && event.getKey() < end) {
            return false;
        }

        events.put(start, end);
        return true;
    }

    public static void main(String[] args) {
        S58MyCalendar calendar = new S58MyCalendar();
        calendar.book(10, 20); // returns true
        calendar.book(15, 25); // returns false
        calendar.book(20, 30); // returns true
    }
}
